#include <stdio.h>
#include <stdlib.h>

typedef struct node{
	int number;
	struct node* next;
} person;

// 初始化约瑟夫环
person* init_loop_list(int n); 

// 寻找节点并删除该节点(从编号为k的人开始，报数为m) 
void find_node_and_kill(person* head,int k,int m); 

int main()
{
	printf("输入圆桌上的人数n:");
	int n;
    scanf("%d",&n);
    person * head=init_loop_list(n);
    printf("从第k人开始报数(k>1且k<%d)：",n);
    int k;
    scanf("%d",&k);
    printf("数到m的人出列：");
    int m;
    scanf("%d",&m);
    find_node_and_kill(head, k, m);
	system("pause");
	return 0;
}

person* init_loop_list(int n)
{
	person* head=(person* )malloc(sizeof(person));
	head->number=1;
	head->next=NULL;
	person* temp=head;
	for(int i=2;i<=n;i++)
	{
		person* body=(person* )malloc(sizeof(person));
		body->number=i;
		body->next=NULL;
		temp->next=body;
		temp=temp->next;
	}
	
	temp->next=head;
	return head;
}

void find_node_and_kill(person* head,int k,int m)
{
	person* tmp=head;
	//找到链表上第一个节点的上一个节点，做好删除准备
	while(tmp->next!=head)
	{
		tmp=tmp->next;
	} 
	
	// 找到编号为k的人
	person* p=head;
	while(p->number!=k)
	{
		tmp=p;
		p=p->next;
	} 
	
	// 从编号为k的人开始，所有符合p->next==p时候，说明链表除了p节点，其他节点已经都出列了
	while(p->next!=p)
	{
		// 找到从p报数1开始，报m的人，而且还要知道m-1的人的位置，方便做删除操作
		for(int i=1;i<m;i++)
		{
			tmp=p;
			p=p->next;
		} 
		
		tmp->next=p->next;
		printf("出列人的编号为:%d\n",p->number);
		free(p);
		p=tmp->next;
	} 
	printf("出列人的编号为:%d\n",p->number);
	free(p);
}
 
